package com.yt.ds.chapter2;

import com.yt.ds.util.SortUtil;

/**
 * @Author: lzf
 * @Date: 2020/7/14 14:22
 * @Description: 快速排序: 和归并排序刚好相反，先排序，再递归下去
 */
public class QuickSort implements Sort {
    @Override
    public Comparable[] sort(Comparable[] array) {
        sort(array, 0, array.length - 1);
        return array;
    }

    private void sort(Comparable[] array, int head, int tail) {
        if (head >= tail) {
            return;
        }
        int mid = partition(array, head, tail);
        // 不是sort(array,head,mid) 的原因是 中间mid不参与排序，因为partition中以他为基准
        sort(array, head, mid - 1);
        sort(array, mid + 1, tail);
    }

    private int partition(Comparable[] array, int head, int tail) {
        Comparable base = array[head];
        int left = head;
        int right = tail + 1;
        while (true) {
            while (array[++left].compareTo(base) < 0) {
                if (left == right) {
                    break;
                }
            }
            while (array[--right].compareTo(base) > 0) {
                if (right == head) {
                    break;
                }
            }
            if (left >= right) {
                break;
            }
            SortUtil.exch(array, left, right);
        }
        SortUtil.exch(array, right, head);
        return right;
    }
}
